from collections import deque
from typing import List


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m = len(grid)
        n = len(grid[0])
        cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = (i,j)
                if 'a'<= grid[i][j] <= 'z':
                    cnt += 1
        inf = float('inf')
        dis = [[[inf for _ in range((1<<cnt))] for _ in range(n)] for _ in range(m)]  # 使用 bitMap记录钥匙拥有情况
        q = deque([(start[0],start[1],0,0)]) # 0 代表没有钥匙
        dis[start[0]][start[1]][0] = 0
        while q:
            x,y,keys,distance = q.popleft()

            if dis[x][y][keys] < distance: continue
            if keys + 1 == (1 << cnt): return distance
            for nx, ny in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
               if nx < 0 or nx >= m: continue
               if ny < 0 or ny >= n: continue
               if grid[nx][ny] == '#': continue
               nkey = keys
               if 'a' <= grid[nx][ny] <= 'z':
                   bit = ord(grid[nx][ny]) - ord('a')
                   nkey |= (1<<bit)
               if 'A' <= grid[nx][ny] <= 'Z':
                   bit = ord(grid[nx][ny]) - ord('A')
                   if not (nkey & (1 << bit)): continue

               if dis[nx][ny][nkey] <= distance + 1: continue
               dis[nx][ny][nkey] = distance + 1
               q.append((nx,ny,nkey,distance+1))
        return -1
if __name__ == '__main__':
    s = Solution()
    r = s.shortestPathAllKeys( ["@.a..","###.#","b.A.B"])
    print(r)